Storage device manufacturers continue to develop new ways to increase the capacity of storage devices. However, for many such storage devices write access performance is not increasing at a rate that is commensurate with the increased storage capacity. As a result, in at least some cases, the amount of time required to sanitize a storage device, by making unreadable (e.g., erasing) all data stored on the storage device, is increasing. Some storage devices (such as Self-Encrypting Drives) are configured to encrypt data using cryptographic keys before storing the data. Such storage devices decrypt the data using the cryptographic keys before transmitting it to a requestor. At least some such storage devices support a cryptographic erase feature, wherein encrypted data stored in a storage device is rendered unreadable by erasing the cryptographic key used to decrypt the data. In at least some cases, such a storage device can be sanitized by erasing the cryptographic key instead of erasing all data stored on the storage device.